package lc;
import java.util.*;
import org.junit.*;

public class Ex518 {
    class Solution1 {
        public int change(int amount, int[] coins) {
            Arrays.sort(coins);
            int len = coins.length;
            int[][] f = new int[len + 1][amount + 1];
            f[len][0] = 1;
            for (int i = len - 1; i >= 0; i--) {
                for (int j = amount; j >= 0; j--) {
                    for (int k = 0; k * coins[i] <= j; k++) {
                        f[i][j] += f[i + 1][j - k * coins[i]];
                    }
                }
            }
            return f[0][amount];
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{1,2,5};
        System.out.println(s.change(5, nums));
    }

    class Solution2 {
        public int change(int amount, int[] coins) {
            Arrays.sort(coins);
            int len = coins.length;
            int[][] f = new int[len + 1][amount + 1];
            f[len][0] = 1;
            for (int i = len - 1; i >= 0; i--) {
                // for (int j = amount; j >= 0; j--) {
                for (int j = 0; j <= amount; j++) {
                    f[i][j] = f[i + 1][j];
                    if (j >= coins[i]) {
                        f[i][j] += f[i][j - amount];
                    }
                }
                    // for (int k = 0; k * coins[i] <= j; k++) {
                    //     f[i][j] += f[i + 1][j - k * coins[i]];
                    // }
                }
            
            return f[0][amount];
        }
    }

    class Solution {
        public int change(int amount, int[] coins) {
            int m = coins.length;
            int[] f = new int[amount + 1];
            //f初始化为全0，表示没有可选择的
            f[0] = 1; //不用凑齐金额
            for (int i = m - 1; i >= 0; i--) {
                for (int j = coins[i]; j <= amount; j++) {
                    if (f[j - coins[i]] > 0) {
                        f[j] = f[j] + f[j - coins[i]];
                    }
                }
            }
            return f[amount];
        }
    }
}
